Related Art 1.
FIG. 66 is a block diagram showing a conventional encoding apparatus.
In FIG. 66, reference numeral 901 indicates a picture element memory for receiving, storing, and outputting the value of a picture element to be encoded (which will be referred to as an encoding picture element, or simply as a picture element) and for outputting the value of at least one encoded picture element already stored in the picture element memory and adjacent to the encoding picture element as the value of a reference picture element.
Reference numeral 907 indicates a predictor for calculating the prediction value for the encoding picture element by referring to the value of the at least one reference picture element.
Reference numeral 931 indicates a prediction error calculator for determining the prediction error by subtracting the prediction value calculated by the predictor 907 from the value of the encoding picture element.
Reference numeral 908 indicates an encoder for encoding the prediction error between the value of the encoding picture element and the prediction value calculated by the predictor 907, and for outputting codewords.
Reference numeral 910 indicates a code buffer for receiving the codewords supplied from the encoder 908 and for outputting a sequence of the codewords as a code in order of the received codewords.
Next, an operation of the conventional encoding apparatus is explained.
The predictor 907 calculates the prediction value from the value of the at least one reference picture element. The calculation method may be implemented in accordance with a predetermined prediction function or by referring to a reference table. The encoder 908 encodes the prediction error (-255.about.+255, inclusive of zero, in the case of one picture element being represented by eight bits) which has been obtained by subtracting the calculated prediction value from the value of an encoding picture element by using a predetermined codeword table.
Related Art 2.
As another conventional related art, conversion of the prediction errors for encoding picture elements and picture elements to be decoded into binary symbol sequences, and encoding and decoding the binary symbol sequences are known. As one of the encoding and decoding methods for binary symbols, the encoding and decoding method disclosed in Japanese Patent Registered No. 1251403 will be described herein.
According to this encoding and decoding method, as shown in FIG. 67, one codeword is allotted to a binary symbol sequence composed of one binary symbol or a plurality of binary symbols. The term "encoding" is used in this specification to mean an operation for determining and allotting a codeword to a sequence of a certain number (which will be hereinafter referred to as the code order) of binary "0" symbols (More Probable Symbols abbreviated to MPSs) or binary "1" symbols (Less Probable Symbol abbreviated to LPSs) occurred, and for outputting the codeword therefor. At the time of encoding, the number of MPSs consecutively occurred is counted by an MPS counter (not shown) inside (or outside) the encoder. The counted value of MPSs is stored in an MPS memory (not shown), and the state numbers of binary symbol sequences (to be described hereafter) are stored in a state-number memory (not shown). The code order may be an integer greater than zero. However, it is assumed herein that the code order is restricted to 2.sup.n (the n-th power of 2). When the number of MPSs consecutively occurred (the count of the MPS counter) has become equal to the code order 2.sup.n, one-bit codeword "0" is allotted to the MPSs. On the other hand, when an LPS has occurred before the number of MPSs consecutively occurred becomes equal to the code order, the number of the MPSs consecutively occurred after outputting the latest codeword before occurring the LPS is expressed in terms of n-bit binary symbols, and, in order to differentiate from the sequence of the MPSs to which the codeword "0" is allotted, the codeword "1" is added to the beginning of the n-bit binary symbols. Accordingly, a codeword of (n+1) bits is allotted to the sequence of MPSs plus the LPS differentiating from the sequence of MPSs to which a codeword of "0" is allotted. The unit of a binary symbol sequence to which a codeword is allotted is referred to as a message. After the codeword is determined and output, the MPS counter is reset. A sequence of codewords output in this way constitutes a code. On the other hand, when a code is to be decoded, the code is supplied to the decoder and divided into individual codewords. Then, a binary symbol sequence is recreated by the decoder, and picture elements are reproduced. In this way, decoding is implemented.
In the aforementioned encoding and decoding method, the code order is changed so as to represent the appropriate code length in accordance with the occurrence probability of one of binary symbols estimated from past data on binary symbol sequences. For this reason, a further excellent encoding efficiency can be obtained.
A first example of the state transition method of determining the code order will be described now.
When a binary symbol sequence is encoded or decoded by an encoder or a decoder, the binary symbol sequence belongs to one of the sixteen states shown in FIG. 68. The code order is determined according to the state to which each binary symbol sequence belongs. It is assumed herein that the initial value of the state number for the encoder or the decoder is set to 0. It is also assumed herein that the MPS counter of the encoder or the decoder is reset at the beginning of the encoding process or the decoding process. During the encoding process or the decoding process, the encoder or the decoder implements state transition when a codeword has been determined. When the number of MPSs consecutively occurred in a binary symbol sequence has become equal to the code order of the binary symbol sequence, the state number of the sequence is increased by one. When an LPS has occurred in a binary symbol sequence before the number of MPSs consecutively occurred becomes equal to the code order of the binary symbol sequence, the state number of the sequence is decreased by one. However, when the number of MPSs consecutively occurred in a binary symbol sequence having the state number 15 has become equal to the code order of the binary symbol sequence, or when an LPS has occurred in a binary symbol sequence having the state number 0, the encoder or the decoder does not implement state transition, and the state number remains unchanged.
According to a second example of the method of determining the code order, there is shown a method in which the numbers of binary symbols "0" and binary symbols "1" which have occurred in a binary symbol sequence, respectively indicated by N(0) and N(1), are counted on both the transmitting side and the receiving side within the same range (such as, for example, within one line) so as to calculate the code order of the binary symbol sequence, based on the result of the count. The method of determining the code order, for example, is disclosed in Japanese Unexamined Patent Publication No. SHO59-27501 (which corresponds to U.S. Pat. No. 4,191,974). The calculation method is expressed by the relation of 2.sup.n+1 N(1)&gt;N(0).gtoreq.2.sup.n N(1). In this case, however, the code order 2.sup.n which varies with state transition of a binary symbol sequence is not less than a predetermined minimum value, nor more than a predetermined maximum value.
It is known that the encoding method shown in FIG. 67 has the following characteristics. Let us assume that a binary information source whose probability of binary symbol "0" and whose probability of binary symbol "1" are p, 1-p (p.gtoreq.1/2) respectively are encoded in accordance with the encoding method shown in FIG. 67. When the occurrence of the binary symbols to be encoded may be random, the order n rendering a maximum code length in each code order minimum fulfills the following expression: EQU {2.sup.n /(2.sup.n +1)}.ltoreq.p&lt;{2.sup.n+1 /(2.sup.n-1 +1)}
Accordingly, by determining n in accordance with the above expression, a substantially optimum code can be selected.
Assuming that the number of binary symbols "0" is N(0) and the number of binary symbols "1" is N(1), the probability p is expressed as follows: EQU p=N(0)/{N(0)+N(1)}
Thus the above expression is reduced to as follows: EQU 2.sup.n N(1).ltoreq.N(0).ltoreq.2.sup.n+1 N(1)
Related Art 3.
Among the conventional encoding apparatuses and the conventional decoding apparatuses, there is an encoding apparatus or a decoding apparatus wherein two encoding or decoding modes such as the mode A and the mode B are provided, for example, and encoding or decoding is implemented by switching between the mode A and the mode B according to the decision whether or not a predetermined condition for the value(s) of reference picture element(s) is satisfied. Basically, if the value(s) of reference picture element(s) satisfies a predetermined condition, encoding or decoding is implemented in the mode A. On the other hand, if the value(s) of reference picture element(s) does not satisfy a predetermined condition, encoding or decoding is implemented in the mode B. Mode switching may be accomplished, for example, in accordance with the method described in "The National Assembly 1016 of the Institute of Electronics and Communication Engineers of Japan held in 1977" as the "run length encoding process according to the encoding start patterns". As shown in FIG. 69, a picture element X is assumed herein to be a picture element to be encoded or decoded (which will be hereinafter simply referred to as a picture element). If the values of reference picture elements a, b, and c adjacent to the picture element X satisfy a predetermined condition "a=b=c", the picture element X and the subsequent picture elements are encoded or decoded continuously in the mode A until the picture element X becomes "X.noteq.a prediction value". When the picture element X occurs that does not coincide with the prediction value, the mode A is switched into the mode B. Then, the picture element X and the subsequent picture elements are encoded or decoded continuously in the mode B. When the values of the reference picture elements a, b, and c satisfy the predetermined condition "a=b=c" again, the mode is switched to the mode A and the subsequent encoding or decoding picture element is encoded or decoded in the mode A.
Related Art 4.
In the following, encoding process and decoding process of a picture in a conventional picture pick-up apparatus is explained referring to drawings. In this related art, encoding process is performed by a picture compression circuit and decoding process is performed by a picture expansion circuit.
FIG. 70 shows a configuration of the picture compression circuit and the picture expansion circuit.
In FIG. 70, the picture compression circuit includes a process for implementing a lossless compression and another process for implementing a lossy compression.
A lossy picture compression means a compressing process where a compressibility of the picture is increased, though a quality of reproduced picture (reproducibility) is decreased.
On the other hand, a lossless picture compression means a compressing process where the quality of reproduced picture (reproducibility) is not decreased, though a compressibility of the picture is less increased than the above lossy picture compression.
A DCT (Discrete Cosine Transform) circuit 951 performs two-dimensional DCT operation on an input picture to divide the picture into two-dimensional spatial frequency components. A quantization circuit 952 quantizes a DCT coefficient. An entropy encoder 953 implements Huffman coding on the quantized DCT coefficient. The lossy picture compression is performed by the DCT circuit 951, the quantization circuit 952 and the entropy encoder 953. A predictor 954 predicts data of a certain picture element by using data of the previous picture element. An entropy encoder 955 implements Huffman coding of a differential between the picture element and the picture element predicted by the predictor 954. In this way, the lossless data compression is implemented by the predictor 954 and the entropy encoder 955. A switch SW1 selects one of the compressing processes: side "a" of the lossless compression; and side "b" of the lossy compression.
The picture expansion circuit includes a process for implementing a lossless expansion and a process for implementing lossy expansion. An entropy decoder 956 and a decoder 957 decode the reversibly compressed data by an inverse operation of the entropy encoder 955 and the predictor 954. An entropy decoder 958, a dequantization circuit 959 and an inverse DCT circuit 960 decode the compressed data by an inverse operation of the DCT circuit 951, the quantization circuit 952 and the entropy encoder 953. A switch SW2 selects one of the expanding processes: side "a" of the lossless expansion; and side "b" of the lossy expansion.
The conventional encoding apparatus which has been described as the related art 1 encodes a prediction error by referring to a predetermined codeword table. Generally, with regard to the picture information, the statistical characteristic of the picture information displayed on a screen varies greatly depending on the part on the screen. In other words, it is known that it occurs that prediction for some part of the picture information displayed on the screen tends to be correct while other part of the picture information displayed on the screen often has great prediction errors. Although the statistical characteristic of the picture information displayed on the screen varies, the encoding apparatus according to the first conventional related art implements encoding by referring to a single codeword table. Thus, it has created a problem in that an encoding efficiency cannot be enhanced.
On the other hand, the encoding method which has been described as the related art 2 is a method of implementing encoding by referring to a plurality of codeword tables and dynamically changing the code order depending on the occurrence probability of the MPS. Consequently, if the statistical characteristic of picture information displayed varies greatly, a more excellent encoding efficiency will be provided with this encoding system than with the encoding apparatus which has been described as the first conventional related art. However, even by using the encoding method according to related art 2, when at least one codeword is allotted to a prediction error for each encoding picture-element, at least one-bit code amount is required for each picture element regardless of whether or not the prediction has proved to be correct (or no prediction error has been produced). Allotting a one-bit or more bits of codeword to a prediction error although the prediction probability exceeds 1/2 means that the actual code amount required is greater than the theoretical minimum code amount (entropy) for the prediction error. In other words, it means that an encoding efficiency is reduced.
According to the aforementioned related art 4, the picture compression circuit (encoding apparatus) and the picture expansion circuit (decoding apparatus) are configured as shown in FIG. 70. The DCT circuit, the quantization circuit and the entropy encoder implement lossy picture compression and lossy picture expansion. On the other hand, the predictor and the entropy encoder implement lossless picture compression and lossless a picture expansion. In this way, the conventional picture pick-up apparatus switches the lossless picture compression circuit and the lossy picture compression circuit according to the condition. In the picture pick-up apparatus, it is mostly required to increase the compressibility of the picture without decreasing the quality of the reproduced picture (reproducibility). Particularly, in the art of a digital camera, the above requests have been highly demanded these days so as to store the picked-up signals in the storage medium and to display the picked-up signals on the monitor. Input information of picture has been increasing because of a large number of picture elements of input picture, color input picture, and multiple gradation of input picture. There is a problem that the conventional picture processing apparatus cannot supply enough compressibility of picture in case of storing such information of picture in a limited capacity of the storage medium.
On handling multimedia information, picture information is transmitted, displayed, or stored together with other information such as audio information, or character information. Picture information occupies higher ratio than other information among such multimedia information, and these days it is required that the compressibility of picture is further increased.